package com.lwx.sort;

public class QSMain {
	public static void main(String[] args) {
		//int[] a = {4, 8, 5, 7, 1, 3, 2, 0};
		int[] a = {5, 4, 8, 5, 7, 1, 3, 2, 0, 9, 11, 1};
		
		quickSort2(a, 0, a.length - 1);
		printArray(a);
	}
	
	public static void quickSort1(int[] a, int start, int end){
		int i = start;
		int j = end;
		int xiabiao = i;
		int pivot = a[i];
		while(i < j){
			for(; j > i; j--){
				if(a[j] < pivot){
					int tmp = a[xiabiao];
					a[xiabiao] = a[j];
					a[j] = tmp;
					xiabiao = j;
					break;
				}
			}
			
			for(;i <= j; i++){
				if(a[i] > pivot){
					int tmp = a[xiabiao];
					a[xiabiao] = a[i];
					a[i] = tmp;
					xiabiao = i;
					break;
				}
			}
		}
		
		if(xiabiao - start > 1){
			quickSort1(a, start, xiabiao - 1);
		}
		
		if(end - xiabiao > 1){
			quickSort1(a, xiabiao + 1, end);
		}
	}
	
	public static void printArray(int[] a){
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i] + ",");
		}
		System.out.println("\n");
	}
	
	public static void quickSort2(int a[], int start, int end) {
        int i = start;
        int j = end;
        if ((a == null) || (a.length == 0))
            return;
        while (i < j) {
            while (i < j && a[i] <= a[j]){/* 以数组start下标的数据为key，右侧扫描 */
                j--;
            }
            if (i < j){/* 右侧扫描，找出第一个比key小的，交换位置 */
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            while (i < j && a[i] < a[j]){/* 左侧扫描（此时a[j]中存储着key值） */
                i++;
            }
            if (i < j){ /* 找出第一个比key大的，交换位置 */
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        if (i - start > 1) {
            quickSort2(a, start, i - 1); /* 递归调用，把key前面的完成排序 */
        }
        if (end - i > 1) {
            quickSort2(a, i + 1, end);/* 递归调用，把key后面的完成排序 */
        }
    }


}
